﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
//class Date
//{
//public:
//	void Init(int year, int month, int day)
//	{
//		_year = year;
//		_month = month;
//		_day = day;
//	}
//	void Print()
//	{
//		printf("%d %d %d\n", _year, _month, _day);
//	}
//
//private:
//	int _year;
//	int _month;
//	int _day;
//};
//int main()
//{
//	Date d1;
//	Date d2;
//	d1.Init(2024, 8, 8);
//	d1.Print();
//	d2.Init(2222, 2, 2);
//	d2.Print();
//	return 0;
//}
//class Stack
//{
//public:
//	void Init(int n = 4);
//
//private:
//	int* _arr;
//	int _capacity;
//	int _top;
//};
//
//void Stack::Init(int n)
//{
//	_arr = (int*)malloc(sizeof(int) * n);
//	_capacity = n;
//	_top = 0;
//}
//int main()
//{
//	Stack st;
//	st.Init();
//	return 0;
//}
//#include<iostream>
//using namespace std;
//// 计算⼀下A/B/C实例化的对象是多⼤？
//class A
//{
//public :
//	void Print()
//	{
//		cout << _ch << endl;
//	}
//private:
//	char _ch;
//	int _i;
//};
//class B
//{
//	public :
//	void Print()
//	{
//		//...
//	}
//};
//class C
//{};
//int main()
//{
//	A a;
//	B b;
//	C c;
//	cout << sizeof(a) << endl;
//	cout << sizeof(b) << endl;
//	cout << sizeof(c) << endl;
//	return 0;
//}
//#include<iostream>
//using namespace std;
//class A
//{
//public :
//	void Print()
//	{
//		cout << "A::Print()" << endl;
//	}
//private:
//	int _a;
//};
//int main()
//{
//	A* p = nullptr;
//	p->Print();
//	return 0;
//}
//#include<iostream>
//using namespace std;
//class A
//{
//public :
//	void Print()
//	{
//		cout << "A::Print()" << endl;
//		cout << _a << endl;
//	}
//private:
//	int _a;
//};
//int main()
//{
//	A* p = nullptr;
//	p->Print();
//	return 0;
//}
//using namespace std;
//class Date
//{
//public:
//	Date(int year=0, int month=0, int day=0)
//	{
//		_year = year;
//		_month = month;
//		_day = day;
//	}
//	void Print()
//	{
//		printf("%d %d %d\n", _year, _month, _day);
//	}
//
//private:
//	int _year;
//	int _month;
//	int _day;
//};
//int main()
//{
//	Date d1;
//	Date d2(1,1,1);
//	d1.Print();
//	d2.Print();
//	return 0;
//}
/////////
//#include<iostream>
//using namespace std;
//class Date
//{
//public :
//	// 1.⽆参构造函数
//	Date()
//	{
//		_year = 1;
//		_month = 1;
//		_day = 1;
//	} 
//	// 2.带参构造函数
//		Date(int year, int month, int day)
//	{
//		_year = year;
//		_month = month;
//		_day = day;
//	} 
//	// 3.全缺省构造函数
//		/*Date(int year = 1, int month = 1, int day = 1)
//		{
//		_year = year;
//		_month = month;
//		_day = day;
//		}*/
//	void Print()
//	{
//		cout << _year << "/" << _month << "/" << _day << endl;	
//	}
//private:
//	int _year;
//	int _month;
//	int _day;
//};
//int main()
//{
//	// 如果留下三个构造中的第⼆个带参构造，第⼀个和第三个注释掉
//	// 编译报错：error C2512: “Date”: 没有合适的默认构造函数可⽤
//	Date d1; // 调⽤默认构造函数
//	Date d2(2025, 1, 1); // 调⽤带参的构造函数
//	d1.Print();
//	d2.Print();
//	return 0;
//}
//#include<iostream>
//using namespace std;
//typedef int STDataType;
//class Stack
//{
//public :
//	Stack(int n = 4)
//	{
//		_a = (STDataType*)malloc(sizeof(STDataType) * n);
//		if (nullptr == _a)
//		{
//			perror("malloc申请空间失败");
//			return;
//		} 
//		_capacity = n;
//		_top = 0;
//	}
//private:
//	STDataType * _a;
//	size_t _capacity;
//	size_t _top;
//};
//
//class MyQueue
//{
//public :
//private:
//	Stack pushst;
//	Stack popst;
//};
//int main()
//{
//	MyQueue mq;
//	return 0;
//}
//#include<iostream>
#include <cassert>
//using namespace std;
typedef int STDatatype;

class Stack
{
public:
	void Init(int n = 4)
	{
		_arr = (STDatatype*)malloc(sizeof(int) * n);
		if (nullptr == _arr)
		{
			perror("malloc fail");
			return;
		}
		_capacity = n;
		_top = 0;
	}
	void Push(STDatatype x)
	{
		if (_top == _capacity)
		{
			int newcapacity = _capacity * 2;
			STDatatype* temp = (STDatatype*)realloc(_arr, sizeof(STDatatype) * newcapacity);
			if (nullptr == temp)
			{
				perror("realloc fail");
				return;
			}
			_arr = temp;
			_capacity = newcapacity;
		}
		_arr[_top++] = x;
	}
	void Pop()
	{
		assert(_top > 0);
		_top--;
	}
	bool Empty()
	{
		return _top == 0;
	}
	int Top()
	{
		assert(_top > 0);
		return _arr[_top - 1];
	}
	void Destroy()
	{
		free(_arr);
		_arr = nullptr;
		_top = _capacity = 0;
	}

private:
	STDatatype* _arr;
	int _capacity;
	int _top;
};
// ⽤最新加了构造和析构的C++版本Stack实现
bool isValid(const char* s) {
	Stack st;
	while (*s)
	{
		if (*s == '[' || *s == '(' || *s == '{')
		{
			st.Push(*s);
		} 
		else
		{
			// 右括号⽐左括号多，数量匹配问题
			if (st.Empty())
			{
			return false;
			} 
			// 栈⾥⾯取左括号
			char top = st.Top();
			st.Pop();
			// 顺序不匹配
			if ((*s == ']' && top != '[')
				|| (*s == '}' && top != '{')
				|| (*s == ')' && top != '('))
			{
				return false;
			}
		} +
			+s;
	} 
	// 栈为空，返回真，说明数量都匹配 左括号多，右括号少匹配问题
	return st.Empty();
} 
//// ⽤之前C版本Stack实现
//bool isValid(const char* s) {
//	ST st;
//	STInit(&st);
//	while (*s)
//	{
//		// 左括号⼊栈
//		if (*s == '(' || *s == '[' || *s == '{')
//		{
//			STPush(&st, *s);
//		} e
//			lse // 右括号取栈顶左括号尝试匹配
//		{
//		if (STEmpty(&st))
//		{
//		STDestroy(&st);
//		return false;
//		} c
//		har top = STTop(&st);
//		STPop(&st);
//		// 不匹配
//		if ((top == '(' && *s != ')')
//			|| (top == '{' && *s != '}')
//			|| (top == '[' && *s != ']'))
//		{
//			STDestroy(&st);
//			return false;
//		} 
//		++s;
//	} 
//	// 栈不为空，说明左括号⽐右括号多，数量不匹配
//	bool ret = STEmpty(&st);
//	STDestroy(&st);
//	return ret;
//} 
int main()
{
	cout << isValid("[()][]") << endl;
	cout << isValid("[(])[]") << endl;
	return 0;
}